import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-03
 * Time: 20:57
 */
public class Solution {
    //多路归并
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int length1=nums1.length;
        int length2=nums2.length;
        //降低后面建堆的时间复杂度
        int minimum=Math.min(length1,k);
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        //建小堆,小堆中存的是下标
        PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->(nums1[a[0]]+nums2[a[1]])-(nums1[b[0]]+nums2[b[1]]));
        for(int i=0;i<minimum;i++){
            queue.add(new int[]{i,0});
        }
        while(ans.size()<k&&!queue.isEmpty()){
            //堆顶元素和一定是最小的
            int[] min=queue.poll();
            List<Integer> list=new ArrayList<>();
            list.add(nums1[min[0]]);
            list.add(nums2[min[1]]);
            if(min[1]<length2-1){
                min[1]++;
                queue.add(new int[]{min[0],min[1]});
            }
            ans.add(list);
        }
        return ans;
    }
}